/*
    二分答案法与相关题目

    前置知识 : 讲解005-对数器、讲解006-基本二分搜索、讲解042-进一步了解对数器

    二分答案法
    1）估计 最终答案可能的范围 是什么，可以定的粗略，反正二分不了几次
    2）分析 问题的答案 和 给定条件 之间的 单调性，大部分时候只需要用到 自然智慧
    3）建立一个f函数，当答案固定的情况下，判断 给定的条件是否达标
    4）在 最终答案可能的范围上不断二分搜索，每次用f函数判断，直到二分结束，找到最合适的答案

    核心点：分析单调性、建立f函数

    注意：
    这个技巧常用且重要，一定要引起重视，非常的美、精妙！
    以后的课还会经常见到

    ================================================

    题目1
    爱吃香蕉的珂珂
    珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉
    警卫已经离开了，将在 h 小时后回来。
    珂珂可以决定她吃香蕉的速度 k （单位：根/小时)
    每个小时，她将会选择一堆香蕉，从中吃掉 k 根
    如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉
    珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
    返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）
    测试链接 : https://leetcode.cn/problems/koko-eating-bananas/

    ================================================

    题目2
    分割数组的最大值(画匠问题)
    给定一个非负整数数组 nums 和一个整数 m
    你需要将这个数组分成 m 个非空的连续子数组。
    设计一个算法使得这 m 个子数组各自和的最大值最小。
    测试链接 : https://leetcode.cn/problems/split-array-largest-sum/

    ================================================

    题目2
    并查集模版(洛谷)
    用递归函数实现路径压缩
    一般情况下小挂大的优化可以省略的写法
    测试链接 : https://www.luogu.com.cn/problem/P3367

    ================================================

    题目3
    机器人跳跃问题
    机器人正在玩一个古老的基于DOS的游戏，游戏中有N+1座建筑，从0到N编号，从左到右排列
    编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位
    起初， 机器人在编号为0的建筑处
    每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E
    下一步它将跳到第个k+1建筑
    它将会得到或者失去正比于与H(k+1)与E之差的能量
    如果 H(k+1) > E 那么机器人就失去H(k+1)-E的能量值
    否则它将得到E-H(k+1)的能量值
    游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位
    现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏
    测试链接 : https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71

    ================================================

    题目4
    找出第K小的数对距离
    数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
    给你一个整数数组 nums 和一个整数 k
    数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length
    返回 所有数对距离中 第 k 小的数对距离。
    测试链接 : https://leetcode.cn/problems/find-k-th-smallest-pair-distance/

    ================================================

    题目5
    同时运行N台电脑的最长时间
    你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries
    其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟
    你想使用这些电池让 全部 n 台电脑 同时 运行。
    一开始，你可以给每台电脑连接 至多一个电池
    然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，
    并连接另一个电池，你可以进行这个操作 任意次
    新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池
    断开连接和连接新的电池不会花费任何时间。注意，你不能给电池充电。
    请你返回你可以让 n 台电脑同时运行的 最长 分钟数。
    测试链接 : https://leetcode.cn/problems/maximum-running-time-of-n-computers/

    开始玩概念了：“碎片拼接”！很秒！难想！

    ================================================

    题目6
    计算等位时间
    给定一个数组arr长度为n，表示n个服务员，每服务一个客人的时间
    给定一个正数m，表示有m个人等位，如果你是刚来的人，每个客人都遵循有空位就上的原则
    请问你需要等多久？
    假设m远远大于n，比如n <= 10^3, m <= 10^9，该怎么做是最优解？
    谷歌的面试，这个题连考了2个月

    ================================================

    题目7
    刀砍毒杀怪兽问题
    怪兽的初始血量是一个整数hp，给出每一回合刀砍和毒杀的数值cuts和poisons
    第i回合如果用刀砍，怪兽在这回合会直接损失cuts[i]的血，不再有后续效果
    第i回合如果用毒杀，怪兽在这回合不会损失血量，但是之后每回合都损失poisons[i]的血量
    并且你选择的所有毒杀效果，在之后的回合会叠加
    两个数组cuts、poisons，长度都是n，代表你一共可以进行n回合
    每一回合你只能选择刀砍或者毒杀中的一个动作
    如果你在n个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了
    但是怪兽如果有中毒效果的话，那么怪兽依然会不停扣血，直到血量耗尽的那回合死掉
    返回至少多少回合怪兽会死掉
    数据范围 : 1<=n<=10^5；1<=hp<=10^9；1<=cuts[i]、poisons[i]<=10^9
    真实大厂算法笔试题

*/